package com.li.algorithm.leetcode.hot100;

public class Test33 {

    /**
     * 方法1:插入排序（超出时间限制）
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     */
//    public ListNode sortList(ListNode head) {
//        //选定当前节点和最小值节点
//        //遍历其后所有节点
//        //小于当前节点的，从最小值节点开始遍历插入
//            //小于最小值，直接插入到最小值左侧，成为最小值
//            //大于最小值，向右遍历，找到合适位置插入
//        //大于当前节点的，不用动
//        //遍历完当前节点，再继续遍历，并将最小值节点设为当前节点
//        ListNode point = head;
//        ListNode min = head;
//        boolean flag = true;
//        ListNode result = null;
//        while (point != null) {
//            ListNode p = point.next;
//            ListNode pre = point;
//            while (p != null) {
//                //p小于当前节点，移动到当前节点前
//                if (p.val < point.val) {
//                    pre.next = p.next;
//                    if (p.val < min.val) {
//                        p.next = min;
//                        min = p;
//                    } else {
//                        for (ListNode t = min; t != point; t = t.next) {
//                            if (t.val <= p.val && t.next.val >= p.val) {
//                                ListNode temp = t.next;
//                                t.next = p;
//                                p.next = temp;
//                                break;
//                            }
//                        }
//                    }
//                    p = pre.next;
//                }
//                //p大于当前节点，不需要移动
//                else {
//                    pre = p;
//                    p = p.next;
//                }
//            }
//            if (flag) {
//                result = min;
//                flag = false;
//            }
//            min = point;
//            point = point.next;
//        }
//        return result;
//    }

    /**
     * 归并排序
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        ListNode p1 = head1, p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                temp.next = p1;
                temp = p1;
                p1 = p1.next;
            } else {
                temp.next = p2;
                temp = p2;
                p2 = p2.next;
            }
        }
        temp.next = p1 == null ? p2 : p1;
        return head.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4);node1.next = node2;
        ListNode node3 = new ListNode(1);node2.next = node3;
//        ListNode node4 = new ListNode(3);node3.next = node4;

        ListNode result = new Test33().sortList(node1);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}
